#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;

void Print(int* pa,int size)
{
    for(int i = 0;i<size;++i)
    {
        cout << pa[i]<< " ";
    }
    cout << endl;
}

void InsertSort(int* pa,int size)
{
    for(int i = 0;i<size-1;++i)
    {
        int end = i;
        int tmp = pa[end+1];
        while(end >= 0)
        {
            if(tmp < pa[end])
            {
                pa[end+1] = pa[end];
                end--;
            }
            else 
                break;
        }
        pa[end+1] = tmp;
    }
}


void ShellSort(int* pa,int size)
{
    int gap = size;
    while(gap > 1)
    {
        gap = gap/3 + 1;
        for(int i = 0;i<size-gap;++i)
        {
            int end = i;
            int tmp = pa[end+gap];
            while(end >= 0)
            {
                if(tmp < pa[end])
                {
                    pa[end+gap] = pa[end];
                    end -= gap;
                }
                else 
                    break;
            }
            pa[end+gap] = tmp;
        }
    }
}


void SelectSort(int* pa,int size)
{
    int left = 0,right = size-1;
    while(left < right)
    {
        int mini = left,maxi = left;
        for(int i = left;i<=right;++i)
        {
            if(pa[i] < pa[mini])
                mini = i;
            if(pa[i] > pa[mini])
                maxi = i;
        }
        swap(pa[left],pa[mini]);
        if(maxi == left)
            maxi = mini;
        swap(pa[right],pa[maxi]);

        left++;
        right--;
    }
}

void BubbleSort(int* pa,int size)
{
    for(int i = 0;i<size-1;++i)
    {
        for(int j = 0;j<size-1-i;++j)
        {
            if(pa[j] > pa[j+1])
                swap(pa[j],pa[j+1]);
        }
    }

}

void AdjustDown(int* pa,int size,int parent)
{
    int child = 2*parent + 1;
    while(child < size)
    {

    if(child + 1 < size && pa[child] < pa[child+1])
    {
        child++;
    }
    
    if(pa[parent] < pa[child])
    {
        swap(pa[parent],pa[child]);
        parent = child;
        child = 2*parent + 1;

    }
        else 
            break;
    }
    

}    

void HeapSort(int* pa,int size)
{
    for(int i = (size-1-1)/2;i >= 0;--i)
    {
        AdjustDown(pa,size,i);
    }

    for(int i = 0;i < size;++i)
    {
        swap(pa[0],pa[size-i-1]);
        AdjustDown(pa,size-1-i,0);
    }
}

void QuickSort1(int* pa,int begin,int end)
{
    if(begin >= end)
        return ;

    int left = begin,right = end;
    int key = pa[left];
    int hole = left;
    while(left < right)
    {
        while(left < right && pa[right] > key)
            --right;
        pa[hole] = pa[right];
        hole = right;

        while(left < right && pa[left] < key)
            ++left;
        pa[hole] = pa[left];
        hole = left;
    }
    pa[hole] = key;

    QuickSort1(pa,begin,hole-1);
    QuickSort1(pa,hole+1,end);
}

void QuickSort2(int* pa,int begin,int end)
{
    if(begin >= end)
        return ;

    int prev = begin,cur = prev + 1;
    int key = pa[begin];
    while(cur <= end)
    {
        if(pa[cur] < key)
        {
            swap(pa[prev],pa[cur]);
            prev++;
        }
        ++cur;
    }
    QuickSort2(pa,begin,prev-1);
    QuickSort2(pa,prev+1,end);
}

void _MergeSort(int* pa,int begin,int end,int* copy)
{
    if(begin >= end)
        return ;

    int mid = (begin+end)/2;
    _MergeSort(pa,begin,mid,copy);
    _MergeSort(pa,mid+1,end,copy);

    int begin1 = begin,end1 = mid;
    int begin2 = mid+1,end2 = end;
    int i = begin;
    while(begin1 <= end1 && begin2 <= end2)
    {
        if(pa[begin1] < pa[begin2])
            copy[i++] = pa[begin1++];
        else 
            copy[i++] = pa[begin2++];
    }

    while(begin1 <= end1 )
    {
        copy[i++] = pa[begin1++];
    }

    while(begin2 <= end2 )
    {
        copy[i++] = pa[begin2++];
    }

    memcpy(pa+begin,copy+begin,(end-begin+1)*sizeof(int));

}

void MergeSort(int* pa,int size)
{
    int* copy = new int[size];
    _MergeSort(pa,0,size-1,copy);

    delete[] copy;
}


void CountSort(int* pa,int size)
{
    int min = pa[0],max = pa[0];
    for(int i = 0; i < size;++i)
    {
        if(pa[i] < min)
            min = pa[i];
        if(pa[i] > max)
            max = pa[i];
    }

    int range = max-min+1;
    int* count = new int[range]{0};
    for(int i = 0;i<size;++i)
    {
        count[ pa[i]-min ]++;
    }

    int j = 0;
    for(int i = 0;i<range;++i)
    {
        while(count[i]--)
        {
            pa[j++] = i+min;
        }
    }

}








